The present invention relates generally to the field of digital data processing apparatus and more particularly to the architecture of a computer system adapted to perform a discrete Fourier transform on a set of input signals representing a complex waveform.
It has long been known that the frequency spectrum of an electrical signal may be derived by application of the Fourier transform to that signal in the time domain. The frequency domain characteristics of a waveform in the time domain provide a very useful analytical tool in a variety of technical disciplines. The pure Fourier analysis of a given periodic function represents the function as the sum of a number, usually infinite, of simple harmonic components. Because the response of a linear dynamic system to a simple harmonic input is usually easy to obtain, the response to an arbitrary complex periodic input can be obtained from its Fourier analysis. Likewise, the field of spectrum analysis, by providing a frequency domain representation of a waveform, facilitates identification of unknown waveforms. Stated differently, if the frequency and the magnitude of the components can be identified, a composite can often be identified or at least usefully characterized. (A typical application would be in human voice recognition.)
In biomedicine, there have been attempts at the Massachusetts Institute of Technology as early as 1950 to adopt the tools of correlation and spectral-density analysis to the interpretations of the electroencephalogram. The Fourier transform is an efficient method for performing correlation and spectral-density analysis of an input signal. This analysis of input signals has not only been attempted with brain waves but also with electrocardiograph signals where reasonable success has taken place in the automatic machine diagnosis of cardiac pathology. These methods have also provided a better basis for the understanding of biological systems through their application to model synthesis.
Analysis of echoes from subterranean structures, such as are produced in seismic technology, has in recent years, been furthered through the use of Fourier transforms on such data. In oceanography, the Fourier transform has been important in the analysis of various time series such as water temperature, salinity, tides, ocean currents, etc.
The post World War II era has also seen the tools of Fourier transforms of time series stimulate new research in the fields of economics. Significant contributions to the literature has been made by R. G. Brown and Arthur D. Little in the field of inventory and production control, and by C. Granger of the Economics Research Program at Princeton University in the application of spectral-analysis to economic time series.
In the prior art, the computation of the Fourier transform for a given data sample has required an elaborate computer means if the results are to be meaningful and quickly obtainable. Large scale general purpose digital computers have been employed for computing the Fourier transform. These systems are exceedingly expensive, not availabe in many instances, require programming and related paper work, do not communicate directly with the scientist or economist user and are generally inefficient in performing the Fourier transform. Recently, time sharing has made the digital computer more accessible but the availability of terminal equipment for two-way communication and especially communication of visual information presents considerable problems and expense. In addition, the availability of telephone lines and the simultaneous use of a central computer by many users makes real time computation exceedingly difficult to realize and presents serious problems of priority and program storage and selections.
With respect to the more efficient usage of the digital computer, special techniques for improving the efficiency of large scale digital computers have been developed. The publication by J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Math of Computation, Vol. 19, pp. 297-301, April 1965, explains such techniques further.
It is also known that an N Point FFT processor may be formed by cascading an A point FFT processor and a B point FFT processor where A.multidot.B=N. When a prime factor algorithm is selected for implementation, that is, when A and B are mutually prime numbers, no intervening phase shifters (or "twiddle factors") are required between the cascaded stages as discussed in an article entitled "Historical Notes on the Fast Fourier Transform" by J. W. Cooley, P. A. W. Lewis and P. D. Welch published in the IEEE transactions on Audio and Electroacoustics, Vol. AU-15, No. 2, June 1967. Therefore, implementation of such prime factor algorithm by cascading a pair of mutually prime FFT processors would not require interstage (or inter-processor) multipliers.